package com.yang.Offer;

/**
 * @Author: yang
 * @Description: class Node {
 *     int val;
 *     Node next;
 *     Node random;
 *
 *     public Node(int val) {
 *         this.val = val;
 *         this.next = null;
 *         this.random = null;
 *     }
 * }
 * @Date: Created in 11:20 2022/8/2
 * @Modified By:
 */
public class Offer35 {
}
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class Offer35Solution {
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }
        // 1.原地赋值原节点并拼接到原节点后面
        Node cur = head;
        while (cur != null){
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = temp.next;
        }
        // 2.赋值random指针
        cur = head;
        while (cur != null){
            if(cur.random != null){
                // 刚开始主要是这里没理解，这里也要让新节点的随机节点指向新节点 而不是老节点的随机节点
                cur.next.random = cur.random.next;
                cur = cur.next;
            }
            cur = cur.next;
        }
        // 3.分离链表 奇数为原链表 偶数为复制后的链表
        Node res = head.next;
        Node pre = head;
        cur = head.next;
        while(cur.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;
    }
}
